For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

1
vote
1answer
46 views

What is the combinatorial proof for the formula of S(n,k) - Stirling numbers of the second kind?

What is the combinatorial proof for the formula of Stirling numbers of the second kind ? i.e. S(n,k) where n is the number of objects and k is the number of parts $${n\brace ...
1
vote
1answer
39 views

Expectation value of number of trials to select all tokens with replacement

(I suppose this is analogous to the coupon collector's problem) I have an infinitely large bag containing tokens marked equiprobably with a number from 1 to $k$ i.e. the probability of selecting any ...
-1
votes
1answer
21 views

Count of boolean functions satisfying a condition [closed]

How to find the number of boolean functions of n variables with the given property: If $f(\alpha) = 1$, where $\alpha \in J^2_n$, then $\forall \beta \in J^2_n : w(\beta) \ge w(\alpha) \implies ...
1
vote
2answers
40 views

Probability of winning (dice)

Given a simple dice $\{1,2,3,4,5,6\}$ : A win is defined as a sequence of $1 \to 2 \to 3$. Every result which "breaks" the sequence (e.g. $1\to 2 \to 1$), is forcing us to start all over again. What ...
3
votes
4answers
63 views

How to solve this combinatorics problem?

As a tourist in NY, I want to go from the Grand Central Station (42nd street and 4th Avenue) to Times Square (47th street and 7th Avenue). I needed my morning coffee, and wanted to go to a Starbucks ...
0
votes
2answers
40 views

Number of permutation with condition

Assume we have a group consisting of both women and men. (In my example it is 67 women and 43 men but that is not important.) The women are indistinguishable and the men are also indistinguishable. ...
3
votes
3answers
60 views

Number of subsets

Let $|X|=n$. How to find all number of subsets $X$ consisting of an even number of elements?
3
votes
2answers
55 views

In how many ways can you group $3$ different numbers from $1$ to $12$ wherein their sum is divisible by $3$?

In how many ways can you group $3$ different numbers from $1$ to $12$ wherein their sum is divisible by $3$? This question is one of the questions asked in a Math contest for intermediate level, ...
2
votes
2answers
66 views

100 prisoners 100 boxes problem

I have some issues with a problem I found on this page: http://www.mast.queensu.ca/~peter/inprocess/prisoners.pdf The problem goes as follows: "A group of 100 condemned prisoners are offered the ...
1
vote
1answer
83 views

Simplify a Combinatorial Sum $\sum_{k=0}^\infty {a\choose k}{b\choose c-k}{d-k\choose e}$

Is there a way to simplify $$\sum_{k=0}^\infty {a\choose k}{b\choose c-k}{d-k\choose e}$$ where $a,b,c,d,e$ are natural numbers? In particular, I would like to see the case for $a=45, ...
7
votes
1answer
100 views

How many ways to add to 32?

I have been presented with a rather complex combination problem. Using only the numbers 2, 4, 6 and 8, how many possible ways can you add up to 32 if the number 4 may only be used no more than once ...
2
votes
1answer
66 views

unbalancing lights

I'm reading the following notes on unbalancing lights, http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf. The question i have is regarding the first page. Where it says Consider a square $n ...
0
votes
2answers
34 views

How many non-negative integer solutions does $x_1+x_2+\cdots+x_n=A$ have?

If I have the Diophantine equation $\displaystyle{\sum_{i=1}^n x_i =A}$, is there a function $f(n,A)$ that will yield the number of non-negative integer solutions of the equation?
1
vote
1answer
19 views

Number of ways of selecting all k-indexed identical items before all k+1 indexed identical items for all k from 1 to n

Suppose we have n indices and we have a specific number of items allotted to this index. Say for 2 balls of colors Blue(B)[1], 4 of color Green(G)[2] and 2 of color Red[3] (I could've just assigned ...
3
votes
2answers
76 views

Partitioning $\{1,2,\cdots ,n\}$ into $2$ sets guarantees $3$ numbers $a,b,c$ in the same set with $ab=c$ for some $n$

(ISL-20-$1988$) Find the least natural number $ n$ such that, if the set $ \{1,2, \ldots, n\}$ is arbitrarily divided into two non-intersecting subsets, then one of the subsets contains 3 distinct ...
9
votes
2answers
225 views
+50

How do I prove this combinatorial identity using inclusion and exclusion principle?

$$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$ Note that we can show this with out using inclusion and exclusion principle by using Pascal's Identity ...
1
vote
1answer
53 views

Count the paths in a graph

For a given graph $G(V,E)$ $V = \{ (x,y) | x = \{0,1, ... , m\}, y = \{0,1, ... , n\} \}$ $E = \{ \{(x,y), (u,v)\} | (x=u \text{ and } |y-v|) = 1 \text{ or } (|x-u| = 1 \text{ and } y=v) \}$ How to ...
0
votes
1answer
57 views

Probability of (A <= B OR A <= C) AND B > C when A, B and C are random integers with different ranges but starting at 0.

I have 3 random integers A, B and C, along with 3 defined integers X, Y and Z: A in [0, X] B in [0, Y] C in [0, Z] All the values that A can take within its defined range are equiprobable. Same goes ...
0
votes
1answer
21 views

How can I count the number of $n$ digit positive integers without a specific digit?

Came across the Kempner Series and was doing a little reading. The proof that the Kempner Series is bounded by 80 requires the fact that the number of $n$ digit positive integers without the digit 9 ...
0
votes
1answer
31 views

Distributing $n$ distinguishable objects into $n$ distinguishable boxes [closed]

I'm taking an introductory statistics course and one of the previous exam questions goes like this: $n$ numbered balls are placed into $n$ distinguishable cells. Find the probability that exactly ...
-4
votes
1answer
47 views

How many ways are there to divide $5$ books amongst $3$ people? [closed]

How many ways are there to divide $5$ books amongst $3$ people, with each person getting zero or more books , given All books are different. All books are identical.
0
votes
2answers
53 views

find the number of ways of selecting 9 balls from 6 red balls 5 white balls and 5 blue balls if each selection contains 3 balls of each colour.

The question in my book has been solved this way $\binom{6}{3}\binom{5}{3}\binom{5}{3}$ but I think that there should only be one way of this combination because no matter how we select 3 balls from ...
0
votes
1answer
31 views

Minimum number of partitions of a set given list of numbers that can't appear in the same partition

I wish to calculate the minimum number of partitions of a set required given a list of pairs of numbers that cannot appear together in the same partition. Example 1: $$S = [1,2,3,4,5,6]\\[5pt] ...
0
votes
3answers
23 views

Calculating the amount of numbers in a range that yields a certain condition

For example: How many numbers in $[40000,70000]$ are there such that the sum of all digits is $12$ and the right most digit is $1$? I cant figure out how to calculate the numbers that the sum of thier ...
0
votes
1answer
42 views

Probability of A > B AND A > C when A, B and C are random integers with different ranges but starting at 0.

I have 3 random integers A, B and C, along with 3 defined integers X, Y and Z: A in [0, X] B in [0, Y] C in [0, Z] All the values that A can take within its defined range are equiprobable. Same goes ...
1
vote
1answer
40 views

Linear extension of a set

I have to find a linear extension of the poset $(X,P)$ where the set $X = \{2,3,10,21,24,50,210\}$ iff $x$ divides $y$. For the answer, I got ...
0
votes
1answer
56 views

From a bag containing $10$ pairs of socks, how many must a person pull out to ensure that they get at least $2$ matching pairs of socks? [closed]

There are $10$ pairs of socks in bag. What is the minimum number of socks that a person should pull out from the bag to ensure that they get at least $2$ matching pairs of socks.
0
votes
0answers
29 views

Looking to get a handle on SSCG(3) (which is much, much larger than TREE(3))

TREE numbers grow rapidly: TREE(1) = 1, TREE(2) = 3, and a lower bound for TREE(3) is A(A(...A(1)...)), where the number of As is A(187196) and A(n) is a version of Ackerman's function. That's ...
2
votes
4answers
83 views

show there exists an integer k such that $2013^k$ ends with '0001'

Prove that there exists an integer k so that $2013^k$ ends with '0001'. we couldn't figure this out. i thought we might try to prove that we can find an integer m such that $m*10^4 +1 = 2013^k$, but ...
-1
votes
2answers
43 views

Should I be using combinations or permutations?

I have a set of $26,000$ values. Each value has the option of being $1$ or $0$. How do I calculate the number of potential combinations of $1$'s and $0$'s that exist for $26,000$ values?
0
votes
0answers
31 views

How many possible Connect 4 end boards are there?

If you search google you can find that there are over 4.5 trillion board combinations, but if i understand correctly there are two differences between this and what I am asking. First this figure ...
1
vote
1answer
33 views

Arranging $8\times 8$ square so that every $2\times 2$ square satisfy $|ab-cd|=1$.

Is it possible to arrange an $8\times 8$ square with numbers $1,2,\ldots,64$ once each so that for every $2\times 2$ square, if the numbers on one diagonal is $a,b$ and the other diagonal $c,d$, then ...
1
vote
0answers
40 views

Deriving deletion-contraction formula from Subgraph Expansion of Chromatic Polynomial

Given a graph $G=(V,E)$, the chromatic polynomial $P(G,q)$ counts the number of $q$-colorings of a graph $G$. It satisfies the deletion-contraction formula: \begin{equation*} P(G,q) = P(G-e, q) - ...
3
votes
3answers
39 views

Trouble Understanding this Combinatorics Problem

Problem: There are 2 girls and 7 boys in a chess club. A team of four persons must be chosen for a tournament, and there must be at least 1 girl on the team. In how many ways can this be done? ...
1
vote
1answer
23 views

combinations of graphs with 2 vertices

I am reading graph theroy. Here author mentions that the number of possible digraphs is truly huge. Each of the $V^2$ possible directed edges (including self-loops) could be present or not, so the ...
-5
votes
1answer
37 views

I need a logic to generate unique number with combination of other numbers [closed]

I have series of numbers 1,2,3,4 upto 10000. I need a logic to generate unique number which is not there in the same series. And it's should not be duplicated with other combinations. Failure Logic, ...
1
vote
2answers
54 views

Tough Polynomial Root Problem

Let $S$ be the set of all polynomials of the form $z^3 + az^2 + bz + c$, where $a$, $b$, and $c$ are integers. Find the number of polynomials in $S$ such that each of its roots $z$ satisfies either ...
2
votes
2answers
20 views

In a circle there are $m$ chords and no $3$ are concurrent, $n$ intersections in the interior. Show there are $m+n+1$ regions dividied by the chords.

In a circle there are $m$ chords such that no $3$ are concurrent and there are $n$ intersections of these chords in the interior of the circle. Prove that the number of regions divided by the ...
11
votes
1answer
72 views

How many unique numbers can be obtained from multiplying two natural numbers less than $N$?

The question seems simple, but I cannot wrap my head around how to properly count it, or even give a good estimate. I can't find the answer either. We have two integer numbers $1 < a,b < N$, ...
2
votes
1answer
39 views

triangulation of the cube of whose vertices are in the set $\lbrace (\pm 1 , \pm 1 , \dots , \pm 1)\rbrace$

Take the cube centered at the origin whose vertices are $\lbrace (1 ,1 , 1) , (-1 ,1 , 1) , (1 ,-1 , 1) , (1 ,1 , -1) , (1 ,-1 , -1) , (-1 ,1 , -1) , (-1 ,-1 , 1) , (-1 ,-1 , -1) \rbrace$. We can ...
1
vote
1answer
28 views

proof that a cycle space is a subspace

I'm looking at the following proof that the cycle space of a graph is indeed a subspace, which I don't believe to be correct. proof: It suffices to prove that $\mathcal{C}$ is closed under $+$ ...
0
votes
0answers
27 views

Show $\sum_{ r = 0}^{n} {(\binom n r)}^{2} = \frac{(2n)!}{(n!)^{2}}$ [duplicate]

How do we show that this identity holds for any n? Any hints or solutions? Show $\sum_{ r = 0}^{n} {(\binom n r)}^{2} = \frac{(2n)!}{(n!)^{2}}$
1
vote
1answer
32 views

coefficient of operator for $B_{n,k}^{x^2}(x)$

We start with the following: $$ (x+z)^2 - x^2 = \sum_{n \geq 1} \frac{z^n}{n!} \frac{d^n}{dx^n}[x^2] $$ $$ (x+z)^2 - x^2 = z(2x+z) $$ $$ z^k(2x+z)^k = \sum_{n \geq k} Y^{\Delta}(n,k,x)z^n $$ Where ...
4
votes
0answers
64 views

About two combinatorial counting problems.

Here are the problems: Suppose $X$ is a set of $n$ elements, and $S_1,...,S_m$ are $m$ subsets of $X$ of average size at least $n/w$. Show that if $m\geq 2kw^k$, then there are $k$ distinct ...
2
votes
5answers
100 views

The number of ways to write $10$ as the sum of five natural numbers not equal to $3$

How many answers are there for the equation $$x_1+x_2+x_3+x_4+x_5=10$$ given that $0\leq x_1, x_2,x_3,x_4,x_5$ and none of them equal to $3$? The numbers $x_1, x_2,x_3,x_4,x_5$ are in $\mathbb{N} $. ...
0
votes
3answers
31 views

Showing that a series solves a recurrence relation

Let: $a_n = a_{n-1}+2a_{n-2} +3\cdot 2^n$, $\displaystyle b_n=4\sum_{k=0}^nk\binom n k$ Show that $b_n$ solves $a_n$ There are no starting conditions for the recurrence, that is how the ...
1
vote
1answer
52 views

Estimation of a probability of marginal values of a random variable

My question is related with this question on combinatorics of 0-1-matrices from MO. Trying to obtain a (asymptotic) lower bound for $\alpha(n)$ by probabilistic approach (see, for instance, “The ...
1
vote
0answers
20 views

Invertible matrices, permutations and leading principal minors

Given an invertible $\{-1,0,1\}$-matrix $A$ (its determinant is $\pm 1$), are there two permutation matrices $P$ and $Q$ such that all the leading principal minors (determinants of the top-left ...
2
votes
0answers
27 views

Performing operations on sides and diagonals of convex polygon

Given a convex $n$-gon with $n\geq 4$. We write a positive number on $2n-3$ segments: all sides, and all diagonals from one vertex. If there is a quadrilateral $ABCD$ such that all sides and the ...
2
votes
1answer
50 views

In how many ways 3 numbers can be chosen from a from the set {1, …, 18} so that their sum is divisible by 3?

In how many ways 3 numbers can be chosen from a from the set {1, ..., 18} so that their sum is divisible by 3? Now, I've seen the solution, but I can't get my head around one detail. The solution ...