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)

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
75 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
206 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
51 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
56 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
52 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
41 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 ...
-1
votes
0answers
30 views

number of solutions of equation $xy \leq n$ where $x>0$ and $y>0$ and $n>0$ [closed]

How do I approach this problem programatically?? Given a positive integer $n$, how many positive integers $(x,y)$ are there such that $x\cdot y\le n$ ?
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
82 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
39 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
22 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
51 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 ...
1
vote
1answer
51 views

Given 3 Red, 3 White, and 3 Blue balls and 3 purple and 1 black urns, how many possible arrangements are there? [closed]

I know for 1 ball of each color, with the same types of urns we can have 16 possible arrangements, but when increasing to 3 balls of each color, how should you approach this?
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 ...
-4
votes
0answers
21 views

combinatorial proof using examples [closed]

$(n-r)\cdot {n\choose r}= (r+1) \cdot{n\choose{r+1}}$ $n \cdot{{n-1}\choose{r-1}} = (n-r+1)\cdot {n\choose{r-1}} $ ${n\choose r}\cdot {r\choose s}= {n\choose s} \cdot {{n-s}\choose{r-s}}$ Please ...
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 ...
3
votes
1answer
40 views

cycle space in graph theory

I read the following definition of the cycle space in a set of notes. Definition (Cycle space): Let $G=(V,E)$ . The cycle space of $G$ is an element of $2^{E}$ denoted $\mathcal{C}$ and is the ...
1
vote
2answers
26 views

Expectation value of number of drawings of increasing sequences of labelled balls from an urn.

An urn contains $n$ balls, labelled from $1$ to $n$. A sequence of drawings with re-insertion is made, until the drawn ball is labelled with a number which is less than or equal to the number of ...
0
votes
2answers
52 views

Applying Inclusion-Exclusion principle

How to apply principle of inclusion-exclusion to this problem? Eight people enter an elevator at the first floor. The elevator discharges passengers on each successive floor until it empties on ...
0
votes
1answer
59 views

game board sequencing [closed]

Consider a graph of a game board. Rounds in the game result in a token moved from a game board location to a game board location, possibly returning to the same one. Let the game board location ...
1
vote
2answers
41 views

Why are these ways of choosing guests to a party the same?

You are having a party, and of your n friends you can invite only k guests. Why are the same number of guest lists as there are of ways of choosing whom not to invite?
0
votes
1answer
35 views

Recurrence relation for a string over the letters $\{A,B,C,D\}$ such that each $A$ appears before $C$

Find a recurrence relation for the number of strings of length $n$ that's composed of the letters $\{A,B,C,D\}$ such that each $A$ appears before $C$. $a_n=\begin{cases} A\text{______} = a_{n-1} ...
2
votes
1answer
23 views

Representing numbers as sum of distinct odd numbers

For each positive integer $n$, let $W(n)$ denote the number of ways to write $n$ as a sum of the numbers $1,3,5,7,\ldots$, using each number at most once. Prove that $W(n)\leq W(n+1)$ for all ...
-3
votes
0answers
15 views

counting problem for falling numbers [duplicate]

A falling number is an integer whose decimal representation has the property that each digit except the units digit is larger than the one to its right. For example 96521 is a falling number but ...
0
votes
1answer
43 views

How many $3$-of-a-kinds are possible if one ace is missing?

So I know how to do the simpler 'How many $3$-of-a-kinds are possible' question - it has been asked on here multiple times too. But what if say an Ace is missing. How would you go about starting the ...